1. Field of the Invention
The present invention relates to a circuit partitioning apparatus and method used in parallel circuit simulation to uniformly partition a target circuit prior to the execution of circuit simulation.
2. Description of the Related Art
To design a circuit, circuit simulation is executed using a computer system so that the circuit exhibits the desired performance. To carry out circuit simulation at a high speed, simulation systems that partition a target system into a plurality of circuits for parallel simulation computations have been proposed. In such simulation systems, the accuracy of simulation and the speed required for computations are significantly affected by the method used to partition a target circuit.
Circuit partitioning methods for efficiently executing circuit simulation in parallel comprise minimizing the number of nodes that connect subcircuits into which a target circuit is partitioned and making the computation time for the simulation of each subcircuit, uniform, that is the load on the computation of the subcircuit. The computation time for simulation, that is, the magnitude of the load on the computation of the subcircuit is hereafter simply referred to as the "magnitude of load".
The conventional predicted value of the magnitude of the load on a subcircuit is the sum (Kt Nt+Kn Nn) of the value Kt Nt of the time required to make a circuit matrix by computing an electric characteristic model of the elements in the subcircuit (model computation time), which value is predicted based on the number of the elements (the number of transistors) Nt, and the value Kn Nn of the matrix computation time predicted based on the number of nodes Kn, wherein Kt and Kn are proportional coefficients (constants).
One example of conventional techniques of this kind is disclosed in Japanese Patent Application Laid Open (Kokai) No. Heisei 1-250173 entitled "Circuit Partitioning Method for Parallel Circuit Simulation". FIG. 8 shows an example of the configuration of a conventional circuit partitioning apparatus used for parallel circuit simulation as described above. A circuit partitioning apparatus 800 shown in the Figure comprises a circuit input section 801, an initial clustering section 802, a min-cut section 803, a partitioned circuit output section 804, a computation time prediction section 805, an element number counting section 806, a node number counting section 807, and a connectivity counting section 808. In addition, the partitioned circuit output section 804 of the circuit partitioning apparatus 800 is connected to a simulation execution section 810 to execute circuit simulation. The simulation execution section 810 is further connected to a simulation result output section 820 for outputting simulation results.
The circuit input section 801 inputs an external circuit description file for a target circuit for simulation. The initial clustering section 802 repeats merging elements with a large connectivity obtained from the circuit data input to the circuit input section 801 in order to partition the circuit into clusters, each comprising a set of elements the sizes of which are as equal as possible. The connectivity of the elements is computed using the connectivity counting section 808. This process is called "initial clustering". The min-unit section 803 collects the clusters into which the circuit is partitioned by the initial clustering section 802 in order to make subcircuits. The subcircuit is made in such a way that the number of nodes connecting the subcircuits is minimized and the size of each subcircuit is equal. This process is called min-cut. The computation time prediction section 805 computes the magnitude of the load on the cluster using the element number counting section 806, which counts the number of the elements included in the subcircuit made by the min-cut section 803 and the node number counting section 807, which counts the number of nodes. The partitioned circuit output section 804 transmits to the simulation execution section 810 the information on the partitioned circuit obtained from the circuit data using the above function execution sections.
FIG. 9 is a flowchart showing the flow of circuit partitioning by the conventional circuit partitioning apparatus. FIG. 9 shows that the circuit partitioning apparatus 800 inputs circuit data (step 901), carries out initial clustering (steps 902 to 907), executes min-cut (steps 908 to 912) to partition the circuit data into subcircuits, and outputs the resulting data to the simulation execution section 810 (step 913). The predicted value of the magnitude of the load on a subcircuit is the sum of the predicted value of the model computation time based on the number of elements and the predicted value of the matrix computation time based on the number of nodes, as described above. One example of such conventional circuit partitioning methods is disclosed in "Development of Parallelism for Circuit Simulation by Tearing", The European Conference on Design Automation, 1993, pp. 12-17 or Japanese Patent Application Laid Open (Kokai) No. Heisei 5-120371 entitled "Circuit Partitioning Apparatus".
The simulation execution section 810 executes parallel circuit simulation for subcircuits obtained by the conventional circuit partitioning technique. In parallel circuit simulation, a modified nodal analysis method is first applied to each subcircuit to obtain a linear simultaneous equation Ax=b. Lower/upper decomposition (hereafter referred to as "LU decomposition") for decomposing a matrix A into the product of triangular matrixes is executed until only the node potential variables of all the internal nodes have been deleted, and only the internal nodes are forward-substituted to generate an equivalent circuit as seen from the external nodes of the subcircuit. Most of the matrix computation time for parallel circuit simulation is the time required for LU decomposition executed to generate an equivalent circuit.
FIG. 10 is a flowchart showing the flow of LU decomposition. In FIG. 10, the computation in step 1005 is called "update operation". Furthermore, the process executed in two inner loops L1 is called "deletion of the i-th variable" or "deletion of the variable corresponding to the i-th node". A sparse matrix technique is generally used for such circuit simulation. If the value of a.sub.ji or a.sub.ik is "0", the update operation in step 1005 is not carried out.
As described above, if circuit simulation is executed in parallel and the magnitude of the load on each subcircuit is equal as indicated by the predicted value, the time required for simulation computations is reduced.
The circuit partitioning technique in the conventional parallel circuit simulation, however, has certain drawbacks, that is, the accuracy of the prediction of the matrix computation time is low because the number of nodes is used as a basis. In other words, since the sparse matrix technique is used for matrix computations in circuit simulation, the matrix computation time is not determined by the number of nodes (that is, the size of the matrix) but by the number of update operations in LU decomposition during simulation.
That is, when the number of the nodes included in the circuit is referred to as "N", the order of the matrix computation time varies in proportion to N.sup..alpha. (1.ltoreq..alpha..ltoreq.3) depending on the circuit. Thus, the prediction of the matrix computation time based on the number of nodes is not very accurate.
In addition, due to the low accuracy of the prediction of the load on the subcircuit, the computation time required to simulate each subcircuit is not equal, resulting in an increase in the time required for parallel circuit simulation. That is, since the circuit is partitioned in such a way that the predicted value of the size of each subcircuit will be as equal as possible, the variation of the computation time for simulation executed for each substrate is large if the predicted value of the size (the sum of the predicted value of the model computation time and the predicted value of the matrix computation time) is not very accurate. Since the time required for parallel circuit simulation is almost equal to the sum of the longest computation time for a particular subcircuit and the computation time for a circuit that couples the subcircuits together, if the computation time for each subcircuit is not equal, the maximum value of the computation time is increased, thereby increasing the time required for parallel circuit simulation.